
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1401. -- Hexagon -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1401: Hexagon</h2><span class=green>Time Limit: </span>3 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>21&nbsp;&nbsp;<span class=green>Solved: </span>11<br>[<a href='submitpage.php?id=1401'>Submit</a>][<a href='problemstatus.php?id=1401'>Status</a>][<a href='bbs.php?id=1401'>Discuss</a>]</center><h2>Description</h2><div class=content>A civil engineer that has recently graduated from the Czech Technical University encountered an interesting problem and asked us for a help. The problem is more of economical than engineering nature. The engineer needs to connect several buildings with an infrastructure. Unfortunately, the investor is not the owner of all the land between these places. Therefore, some properties have to be bought first. 
The land is divided into a regular ``grid" of hexagonal parcels, each of them forms an independent unit and has the same value. Some of the parcels belong to the investor. These parcels form four connected areas, each containing one building to be connected with the others. Your task is to find the minimal number of parcels that must be acquired to connect the four given areas. 
 
The whole land also has a hexagonal shape with six sides, each consisting of exactly H parcels. The above picture shows a land with H = 4 , parcels with letters represent the four areas to be connected. In this case, it is necessary to buy four additional parcels. One of the possible solutions is marked by crosses. 
简单描述：给你一个六边形，这个六边形由很多个小六边形构成，如图．这个六边形中有4个连通区域(图中黑色区域)，现在你的任务是再选择最少个数的小六边形使得四块区域连通．

</div><h2>Input</h2><div class=content>The input contains several scenarios. Each scenario begins with an integer number H , which specifies the size of the land, 2 H 20 . Then there are 2*H - 1 lines representing individual ``rows" of the land (always oriented as in the picture). The lines contain one non-space character for each parcel. It means the first line will contain H characters, the second line H + 1 , and so on. The longest line will be the middle one, with 2*H - 1 characters. Then the ``length" descends and the last line contains H parcels, again. 
The character representing a parcel will be either a dot (``.") for the land that is not owned by the investor, or one of the uppercase letters ``A", ``B", ``C", or ``D". The areas of parcels occupied by the same letter will always be connected. It means that between any two parcels in the same area, there exists a path leading only through that area. 
Beside the characters representing parcels, the lines may contain any number of spaces at any positions to improve ``human readability" of the input. There is always at least one space between two letters (or the dots). After the land description, there will be one empty line and then the next scenario begins. The last scenario is followed by a line containing zero. 
</div><h2>Output</h2><div class=content>For each scenario, output one line with the sentence ``You have to buy P parcels.", where P is the minimal number of parcels that must be acquired to make all four areas connected together. 
Areas are considered connected, if it is possible to find a path between them that leads only through parcels that have been bought. 
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4 <br />
    B . . C <br />
   . . . . C <br />
  . A . . C . <br />
 . A A . . . .<br />
  . A . . . . <br />
   . . . D D <br />
    . . . . <br />
0<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>You have to buy 4 parcels.<br />
</span></div><h2>HINT</h2>
			<div class=content><p><img border="0" src="images/1401.jpg"><br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=HNOI2009集训Day1'>HNOI2009集训Day1</a></p></div><center>[<a href='submitpage.php?id=1401'>Submit</a>][<a href='problemstatus.php?id=1401'>Status</a>][<a href='bbs.php?id=1401'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
